(Problem) 010 Summation of primes

Project Euler

• 공식 홈페이지 - projecteuler.net
• 한글 번역 - projecteuler @kr
• (HackerRank) ProjectEuler+ - hackerrank.com

Problem

Problem list

• No 10 : Summation of primes
  • HackerRank : Project Euler #4: Summation of primes

Summation of primes

problem <번역>

solution

Simple Code

sympy 모듈을 사용하면 매우 간단하게 구할 수 있다. 매우 깔끔해서 좋다ㅎㅎㅎ
하지만 이렇게 답을 구하면 문제의 의미가 없어지기 때문에 소수를 구할 때 자주 사용했던 에라토스테네스의 체를 구현하겠다.

010_summation_of_primes.py

from sympy import primerange


def summation_of_primes(n):
  return sum(primerange(1, n))


print(summation_of_primes(2000000))  

010_summation_of_primes_with_eratosthenes.py

def summation_of_primes_with_eratosthenes(n):
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    total = 0

    for prime, isPrime in enumerate(sieve):
        if isPrime:
            total += prime
            for idx in range(prime*prime, n + 1, prime):
                sieve[idx] = False

    return total


print(summation_of_primes_with_eratosthenes(2000000))  

---

HackerRank

으… 반복할 때마다 소수의 합을 계산하면 Test case 5, 6에서 Runtime error가 뜬다.
그래서 1,000,000 까지 소수의 합을 리스트에 미리 저장해 놓고 테스트 케이스마다 그 리스트의 해당 인덱스를 호출하는 식으로 통과했다.

010_for_HacerRank.py

def summation_of_primes_with_eratosthenes(n):
  sieve = [True] * (n + 1)
  sieve[0] = sieve[1] = False
  total = [0] * (n + 1)

  for prime, isPrime in enumerate(sieve):
      if isPrime:
          total[prime] += total[prime - 1] + prime
          for idx in range(prime*prime, n + 1, prime):
              sieve[idx] = False
      else:
          total[prime] = total[prime - 1]

  return total


if __name__ == '__main__':
  summations = summation_of_primes_with_eratosthenes(1000000)
  for _ in range(int(input())):
      print(summations[int(input())])
 

더 좋은 방법이 있는 것인가…?